package com.example.graph;

import java.util.Arrays;

/**
 * 给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连分量的数目。
 *
 * 示例1:
 * 输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]
 * 输出: 2
 *
 * 示例二:
 * 输入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
 * 输出:  1
 */
public class Leetcode323_CountComponents {
    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}, {3, 4}};
        int n = 5;

        edges = new int[][] {{0, 1}, {1, 2}/*, {2, 3}, {3, 4}*/};
        System.out.println(new Solution().countComponents(n, edges));

    }

    static class Solution {

        public int countComponents2(int n, int[][] edges) {
            if (edges.length >= n - 1) return 1;
            return n - edges.length;
        }

        /**
         * 解法一:并查集
         * @param n
         * @param edges
         * @return
         */
        public int countComponents1(int n, int[][] edges) {
            UnionFindSet uf = new UnionFindSet(n);
            // 遍历边,将边的两个节点进行合并
            for (int[] edge : edges) {
                uf.union(edge[0], edge[1]);
            }
            return uf.count;
        }
        
        class UnionFindSet {
            int[] parents; // 记录每个节点的父节点
            int[] ranks; // 记录每个节点的秩
            int count; // 集合的数量

            public UnionFindSet(int nodeSize) {
                parents = new int[nodeSize];
                ranks = new int[nodeSize];
                Arrays.fill(ranks, 1); // 初始化每个节点的秩为1
                count = nodeSize;
                for (int i = 0; i < parents.length; i++) {// 将每个节点的父节点置为自己
                    parents[i] = i;
                }
            }

            /**
             * 递归寻找父节点并完成路径压缩
             * @param node
             * @return
             */
            public int find(int node) {
                if (parents[node] != node) {// 父节点不是本身不是根节点
                    // 递归地查找父节点的父节点，并将其作为当前节点的父节点
                    // 最终，每个节点的父节点都将直接指向代表节点，形成一个菊花图。
                    parents[node] = find(parents[node]);
                }
                return parents[node];
            }

            public void union(int node1, int node2) {
                int p1 = find(node1);
                int p2 = find(node2);
                if (p1 != p2) { // 两个节点的父节点不相同需要合并
                    if (ranks[p1] > ranks[p2]) {
                        parents[p2] = p1;
                    } else if (ranks[p1] < ranks[p2]) {
                        parents[p1] = p2;
                    } else { // 秩相同，合并谁都可以，但是对应的秩要加1
                        parents[p2] = p1;
                        ranks[p1]++;
                    }
                    --count;
                }

            }
        }


        public int countComponents(int n, int[][] edges) {
            return countComponents1(n, edges);
        }
    }
}
